Home > Search Results: keywords:"graphs|graph homomorphism|complexity|signed graphs|covering projections|colouring|acyclic colouring"
Search:
Search Tips :: Advanced Search
Search collections:
Sort by: Display results: Output format:
National Repository of Grey Literature 2 records found  Search took 0.00 seconds. 
Structure and complexity of homomorphisms
 Bok, Jan ; Nešetřil, Jaroslav (advisor)
This thesis is concerned with computational complexity aspects of graph homomorph- isms and related concepts. We are mainly interested in various polynomial time versus NP-complete dichotomies. These results are especially popular thanks to the seminal result of Hell and Nešetřil providing the complexity dichotomy for graph homomorph- ism problems and the recent breakthrough result proving the complexity dichotomy for constraint satisfaction problems. The thesis is divided into three parts, all unified by the common goal to provide complexity classifications of various graph homomorphism problems. The first part is about list homomorphism problems for signed graphs. We study the complexity of such problems and obtain a structural description and dichotomy first for the case of targets being signed trees and then for the so-called separable graphs. The second part focuses on graph covering projections, also known as locally bijective homomorphisms. To the best of our knowledge, we are the first to initiate cataloguing the complexity of the corresponding problems for (mutli)graphs with semi-edges. We have three larger goals here. (1) Providing the complete dichotomy for one- and two- vertex target graphs. (2) Discuss and propose the right definition of graph cover in the case of disconnected targets. (3)...
Detailed record
Structure and complexity of homomorphisms
 Bok, Jan ; Nešetřil, Jaroslav (advisor) ; Golovach, Petr (referee) ; Proskurowski, Andrzej (referee)
This thesis is concerned with computational complexity aspects of graph homomorph- isms and related concepts. We are mainly interested in various polynomial time versus NP-complete dichotomies. These results are especially popular thanks to the seminal result of Hell and Nešetřil providing the complexity dichotomy for graph homomorph- ism problems and the recent breakthrough result proving the complexity dichotomy for constraint satisfaction problems. The thesis is divided into three parts, all unified by the common goal to provide complexity classifications of various graph homomorphism problems. The first part is about list homomorphism problems for signed graphs. We study the complexity of such problems and obtain a structural description and dichotomy first for the case of targets being signed trees and then for the so-called separable graphs. The second part focuses on graph covering projections, also known as locally bijective homomorphisms. To the best of our knowledge, we are the first to initiate cataloguing the complexity of the corresponding problems for (mutli)graphs with semi-edges. We have three larger goals here. (1) Providing the complete dichotomy for one- and two- vertex target graphs. (2) Discuss and propose the right definition of graph cover in the case of disconnected targets. (3)...
Detailed record

Interested in being notified about new results for this query?
Subscribe to the RSS feed.
Digital Repository :: Search :: Submit :: Personalize :: Help
Powered by Invenio v1.1.2
Maintained by admin.invenio@techlib.cz
This site is also available in the following languages:
Česky  English